package pers.tz.题目.leetcode.链表;

import pers.tz.common.ListNode;
import pers.tz.common.ListUtils;

/**
 * @author irony
 * @date 2024-03-12
 */
public class leetcode_0021_合并两个有序链表 {
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
// 示例 1：
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
//
// 示例 2：
//输入：l1 = [], l2 = []
//输出：[]
//
// 示例 3：
//输入：l1 = [], l2 = [0]
//输出：[0]
//
// 提示：
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列

    public static void main(String[] args) {
        ListNode l1 = ListUtils.generateList(3, true, 1, 10);
        ListNode l2 = ListUtils.generateList(2, true, 1, 10);
        ListUtils.printList(l1, l2);

        ListUtils.printList(mergeTwoLists(l1, l2));
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }

        // 锁死头节点
        ListNode head = list1.val < list2.val ? list1 : list2;

        // 三个指针，两个分别指向各自链表的比较节点，一个指向决定节点，决定下个节点指向哪里
        ListNode compareCur1 = head.next;
        ListNode compareCur2 = list1.val < list2.val ? list2 : list1;
        ListNode modifyCur = head;

        while (compareCur1 != null && compareCur2 != null) {
            if (compareCur1.val <= compareCur2.val) {
                modifyCur.next = compareCur1;
                compareCur1 = compareCur1.next;
            } else {
                modifyCur.next = compareCur2;
                compareCur2 = compareCur2.next;
            }
            modifyCur = modifyCur.next;
        }

        modifyCur.next = compareCur1 != null ? compareCur1 : compareCur2;
        return head;
    }
}
